package com.cwj.lab2;

import com.cwj.lab1.LinkStack;
import com.cwj.lab1.QueueCy;

import java.util.Stack;

/**
 * 链式结构的二叉树
 * */

public class BT<T> {
    //树结点
    class Node {
        T data;
        Node lef;
        Node rig;

        public Node(T data, Node lef, Node rig) {
            this.data = data;
            this.lef = lef;
            this.rig = rig;
        }
    }
//树的根结点
    private Node root;

    /**
     * 括号表示法识别
     * */
    public void initTree(String str) {
        //即如果str无效就返回空
        if (str == null || str.length() == 0) {
            root = null;
            return;
        }
        //用了存储父节点的
        Stack<Node> sta = new Stack<>();
        boolean isLef = true;//其是用来标识该结点是左子结点还是右子结点
        Node nn = null;
        //每次对一个符号进行判别
        for (int i = 0; i < str.length(); i++) {
            Character c = str.charAt(i);
            //若为字母，就必为结点，剩下就是将其接入父节点
            if (c <= 'Z' && c >= 'A') {
                nn = new Node((T) c, null, null);
                //栈为空，字母没有父节点，即为根结点
                if (sta.empty()) {
                    root = nn;
                    //sta.add(root);
                } else {
                    //栈顶元素即为其父结点
                    if (isLef) {
                        sta.peek().lef = nn;
                    } else {
                        sta.peek().rig = nn;
                    }
                }
            } else if (c == '(') {
                //若为括号，那么为父结点，可以入栈，其首先处理左结点指针
                sta.add(nn);
                isLef = true;
            } else if (c == ')') {
                //其久标识栈顶元素的儿子指针已经搞好了；
                sta.pop();
            } else if (c == ',') {
                //逗号即，要设置右结点指针了
                isLef = false;
            }
        }
    }
//调试的函数
    public void show() {
        System.out.print(this.toString());
    }

    public void showln() {
        this.show();
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        toString(this.root, sb);
        return sb.toString();
    }

    public void toString(Node root, StringBuffer sb) {
        if (root == null) {
            return;
        }
        sb.append(root.data);
        if (root.lef != null || root.rig != null) {
            sb.append('(');
            toString(root.lef, sb);
            if (root.rig != null) {
                sb.append(',');
                toString(root.rig, sb);
            }
            sb.append(')');
        }
    }
/**
 * 根据值寻找其结点的值
 * 是否为对称树(默认空树为对称树)
 * 其原理在前面的原理部分就有说明了
 */
    public boolean isSymmetricTree() {
        if (root == null) {
            return true;
        }
        return this.isSymmetricTree(root.lef, root.rig);
    }
    private boolean isSymmetricTree(Node lef, Node rig) {
        if (lef == null && rig != null || lef != null && rig == null) {
            return false;
        }
        if (lef == null) {
            return true;
        }
        if (lef.data != rig.data) {
            return false;
        }
        if (!isSymmetricTree(lef.lef, rig.rig)) {
            return false;
        }
        if (!isSymmetricTree(lef.rig, rig.lef)) {
            return false;
        }
        return true;
    }

    /**求结点总数数*/
    public int nodeSum() {
        return nodeSum(this.root);
    }

    private int nodeSum(Node root) {
        if (root == null) {
            return 0;
        }
        return nodeSum(root.lef) + nodeSum(root.rig) + 1;
    }

    /**求叶子节点个数*/
    public int lfNodeSum() {
        return lfNodeSum(this.root);
    }

    private int lfNodeSum(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.lef == null && root.rig == null) {
            return 1;
        }
        return lfNodeSum(root.lef) + lfNodeSum(root.rig);
    }
/**
 * 计算树的高度
 * */
    public int getHigh() {
        return getHigh(root, 0);
    }

    private int getHigh(Node root, int high) {
        if (root == null) {
            return high;
        }
        return Math.max(getHigh(root.lef, high + 1), getHigh(root.rig, high + 1));
    }

    /**二叉树的度为总结点-1；*/
    public int getDegree() {
        return this.nodeSum() - 1;
    }
/**
 * 前序遍历,节点操作结果为打印其顺序的线性关系
 * 递归版本
 */
    public String preOrder() {
        StringBuffer sb = new StringBuffer();
        preOrder(root, sb);
        return sb.toString();
    }

    private void preOrder(Node root, StringBuffer sb) {
        if (root == null) {
            return;
        }
        sb.append(root.data);
        preOrder(root.lef, sb);
        preOrder(root.rig, sb);
    }
    /**
     * 前序遍历,节点操作结果为打印其顺序的线性关系
     * 迭代版本
     */
    //迭代版
    public String preOrder2() {
        if (this.root == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        LinkStack<Node> sta = new LinkStack<>();
        Node node = null;
        sta.push(this.root);
        while (!sta.isEmpty()) {
            node = sta.pop();
            sb.append(node.data);
            if (node.rig != null) {
                sta.push(node.rig);
            }
            if (node.lef != null) {
                sta.push(node.lef);
            }
        }
        return sb.toString();
    }

    /**
     * 中序遍历,节点操作结果为打印其顺序的线性关系
     * 递归版本
     */
    public String midOrder() {
        StringBuffer sb = new StringBuffer();
        midOrder(this.root, sb);
        return sb.toString();
    }

    private void midOrder(Node root, StringBuffer sb) {
        if (root == null) {
            return;
        }
        midOrder(root.lef, sb);
        sb.append(root.data);
        midOrder(root.rig, sb);
    }
    /**
     * 中序遍历,节点操作结果为打印其顺序的线性关系
     * 迭代版本
     */
    public String midOrder2() {
        StringBuffer sb = new StringBuffer();
        if (this.root == null) {
            return null;
        }
        LinkStack<Node> sta = new LinkStack<>();
        Node ptr = this.root;
        while (ptr != null || !sta.isEmpty()) {
            while (ptr != null) {
                sta.push(ptr);
                ptr = ptr.lef;
            }
            if (ptr == null && !sta.isEmpty()) {
                ptr = sta.pop();
                sb.append(ptr.data);
                ptr = ptr.rig;
            }
        }
        return sb.toString();
    }
    /**
     * 后序遍历,节点操作结果为打印其顺序的线性关系
     * 递归版本
     */
    public String postOrder() {
        StringBuffer sb = new StringBuffer();
        postOrder(this.root, sb);
        return sb.toString();
    }

    private void postOrder(Node root, StringBuffer sb) {
        if (root == null) {
            return;
        }
        postOrder(root.lef, sb);
        postOrder(root.rig, sb);
        sb.append(root.data);
    }
    /**
     * 后序遍历,节点操作结果为打印其顺序的线性关系
     * 迭代版本
     */
    public String postOrder2() {
        if (this.root == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        LinkStack<Node> sta = new LinkStack<>();
        Node ptr = this.root;
        while (ptr != null || !sta.isEmpty()) {
            while (ptr != null) {
                sta.push(ptr);
                ptr = ptr.lef;
            }
            if (ptr == null) {
                ptr = sta.peek();
                if (ptr == null) {
                    sta.pop();
                    sb.append(sta.pop().data);
                } else {
                    sta.push(null);
                    ptr = ptr.rig;
                }
            }
        }
        return sb.toString();
    }

    //二叉树的构造
    //即通过传入前序遍历和中序遍历的表达式来构建一颗树
    //这里因为Node是定义在BT类的内部类，所以最好就不要返回Node,所以函数就设置为没有返回值的，所以就函数的副作用变为修改私有遍历this.root
    //另外因为语言是java不需要内层释放，如果为c++那么在修改this.root前要记得消耗原来的树，销毁的方法也很简单，就用递归即可；
    public void initPreMid(String preStr, String midStr) {
        this.root = createPreMid(preStr, 0, midStr, 0, midStr.length() - 1);
    }

    private Node createPreMid(String preStr, int start, String midStr, int lef, int rig) {
        if (rig < lef) {
            return null;
        }
        if (start >= preStr.length()) {
            return null;
        }
        int i = 0;
        Character target = preStr.charAt(start);
        for (i = lef; i <= rig; i += 1) {
            if (midStr.charAt(i) == target) {
                break;
            }
        }
        Node node = new Node((T) target, null, null);
        node.lef = createPreMid(preStr, start + 1, midStr, lef, i - 1);
        node.rig = createPreMid(preStr, start + 1 + (i - lef), midStr, i + 1, rig);
        return node;
    }

    //传入后序遍历和中序遍历的表达式来构建一颗树
    public void initPostMid(String PostStr, String midStr) {
        this.root = createPostMid(PostStr, PostStr.length() - 1, midStr, 0, midStr.length() - 1);
    }

    private Node createPostMid(String postStr, int start, String midStr, int lef, int rig) {
        if (rig < lef) {
            return null;
        }
        if (start < 0) {
            return null;
        }
        int i;
        Character target = postStr.charAt(start);
        for (i = lef; i <= rig; i += 1) {
            if (midStr.charAt(i) == target) {
                break;
            }
        }
        Node node = new Node((T) target, null, null);
        node.lef = createPostMid(postStr, start - 1 - (rig - i), midStr, lef, i - 1);
        node.rig = createPostMid(postStr, start - 1, midStr, i + 1, rig);
        return node;
    }

    /**
     * 求最近公共祖先
     * */
    public Node lca(T one, T two) {
        return lca(this.root,one,two);
    }

    private Node lca(Node root, T one, T two) {
        //如果root为空，就证明到现在还没有找到结点，而如果其是其中任意一个结点那么就直接返回，那个结点就好
        if(root==null||root.data.equals(one)||root.data.equals(two)){
            return root;
        }
        //如果子树均有结点传来，那么就证明其是公共祖先了，否则就继续往上传递，传递非空子树，或是均空，就传递null
        Node lef=null,rig=null;
        lef=lca(root.lef,one,two);
        rig=lca(root.rig,one,two);
        if(rig!=null&&lef!=null){
            return root;
        }else if(lef!=null){
            return lef;
        }else{
            return rig;
        }
    }
    /**
     * 树的左视图
     * 层序遍历，但仅仅需要每一层的第一个结点即可
     * */
    public String lefTree(){
        StringBuffer sb=new StringBuffer();
        QueueCy<Node>que=new QueueCy<>();
        que.push(this.root);
        Node nn=null;
        while(!que.isEmpty()){
            int len=que.size();
            for(int i=0;i<len;i+=1){
                nn=que.pop();
                if(i==0){
                    sb.append(nn.data);
                }
                if(nn.lef!=null){
                    que.push(nn.lef);
                }
                if(nn.rig!=null){
                    que.push(nn.rig);
                }
            }
        }
        return sb.toString();
    }
}



